/**
 * 该模块实现了一个泛型 FIFO 队列集合。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */
module system.collections.Queue;

import system.Array;
import system.Traits;
import system.Exception;
import system.collections.IQueue;
import system.collections.ICollection;
import system.collections.IEnumerable;
import system.collections.IEnumerator;
import system.collections.EqualityComparer;

version(unittest)
{
	import system.collections.ArrayList;
}

/**
 * 表示对象的可自动扩容的先进先出泛型集合。
 * Comments:
 * 		队列在按接收顺序存储消息方面非常有用，以便于进行顺序处理。
 * 		存储在 Queue(T) 中的对象在一端插入，从另一端移除。
 *
 * 		Queue(T) 的容量是指 Queue(T) 可以容纳的元素数。
 * 		当向 Queue(T) 添加元素时，将通过重新分配内部数组，根据需要自动增大容量。
 * 		可通过调用 trimExcess 来减少容量。
 *
 * 		Queue(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
 */
public class Queue(T):IEnumerable!(T), ICollection!(T), IQueue!(T)
{
	private T[] theArray;
	private int theSize;
	private int theHead;
	private int theTail;
	private int theVersion;

	private const int defaultCapacity = 16;

	/**
	 * 初始化 Queue(T) 类的新实例，该实例为空并且具有默认初始容量 4 。
	 * Comments:
	 * 		此构造函数的运算复杂度是 O(n)，n 为默认初始容量 4 。
	 */
	public this()
	{
		this(defaultCapacity);
	}

	/**
	 * 初始化 Queue(T) 类的新实例，该实例为空并且具有指定的初始容量。
	 * Params:
	 * 		intialCapacity = 可包含的初始元素数。
	 */
	public this(int initialCapacity)
	in
	{
		assert(initialCapacity >= 0);
	}
	body
	{
		theArray = new T[initialCapacity];
	}

	/**
	 * 初始化 Queue(T) 类的新实例，该实例包含从指定的集合中复制的元素并且其容量足以容纳所复制的元素数。
	 * Params:
	 * 		enumerable = 其元素被复制到新的 Queue(T) 中的集合。
	 */
	public this(IEnumerable!(T) enumerable)
	in
    {
        assert( enumerable !is null, "Parameter enumerable can not be null." );
    }
	body
	{
		theArray = new T[defaultCapacity];
		foreach(item; enumerable)
		{
			enqueue(item);
		}
	}

	/*
	 * 实现 IEnumerable(T) 接口。
	 */

	/**
     * Throws:
     * 		InvalidOperationException，当在遍历对象时修改了集合。
     */
	public final class Enumerator : IEnumerator!(T)
	{
		private Queue!(T) theQueue;
		private int theIndex;
		private int theVersion;

		private const int NotStarted = -2;
		private const int Finished = -1;

		package this(Queue!(T) queue)
		{
			this.theQueue = queue;
			theIndex = NotStarted;
			theVersion = queue.theVersion;
		}

		/*
		 * 实现 IEnumerator(T) 接口。
		 */

		public bool moveNext()
		{
			if(this.theVersion != this.theQueue.theVersion)
				throw new InvalidOperationException("Enumerate failed.");
			if(this.theIndex == NotStarted)
				theIndex = theQueue.theSize;

			return theIndex != Finished && --theIndex != Finished;
		}

		public T current()
		{
			if(theIndex < 0)
				throw new InvalidOperationException("Enumerate failed.");
			return theQueue.theArray[(theQueue.theSize - 1 - theIndex + theQueue.theHead) % theQueue.theArray.length];
		}

		public void reset()
		{
			if(theVersion != theQueue.theVersion)
				throw new InvalidOperationException("Enumerate failed.");
			theIndex = NotStarted;
		}
	}

	public final Enumerator  getEnumerator()
	{
		return new Enumerator(this);
	}

	public final int opApply(int delegate(ref T value) dg)
    {
        auto scope enumerator = new Enumerator(this);
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
    }

	/*
	 * 实现 ICollection(T) 接口。
	 */

	/**
	 * 查看队列是否为空。
	 */
	public bool isEmpty()
	{
		return theSize == 0;
	}

	/**
	 * 获取队列中包含的元素数。
	 * Comments:
	 * 		队列的容量是指队列可存储的元素数。count 是队列中的实际元素数。
	 * 		容量始终大于或等于 count。
	 * 		如果添加元素时 count 超过容量，则通过在复制旧元素和添加新元素之前自动重新分配内部数组来增加容量。
	 * 		检索此属性的值的运算复杂度是 O(1)。
	 */
	public final int count()
	{
		return theSize;
	}

	/**
	 * 获取队列是否只读。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	public final bool add(T item)
	{
	    return tryEnqueue(item);
	}

	/**
	 * 不支持该操作。
	 * Throws: NotSupportedException.
	 * Comments:
	 * 		有此方法纯粹是为了实现接口所需。
	 * 		开发人员应当使用实现 IQueue(T) 接口的 dequeue 方法代替该方法。
	 */
	public final bool remove( T item )
	{
		throw new NotSupportedException();
	}

	/**
	 * 确定某元素是否在队列中。
	 * Params:
	 * 		item = 要在队列中定位的对象。对于引用类型，该值可以为 null 。
	 * Returns:
	 * 		如果在队列中找到 item，则为 true；否则为 false。
	 * Comments:
	 * 		此方法使用默认的相等比较器 DefaultEqualityComparer(T) 来确定 T（队列中的值的类型）是否相等。
	 */
	public final bool contains(T item)
	{
		auto index = theHead;
		auto size = theSize;

		auto comparer = DefaultEqualityComparer!(T).getInstance();

		foreach(value; this)
		{
			if(comparer.equals(value, item))
				return true;
		}

		return false;
	}

	/**
	 * 从指定数组索引开始将队列元素复制到现有一维 Array 中。
	 * Comments:
	 * 		元素按照枚举数循环访问队列的顺序复制到 Array 中。
	 */
	public final void toArray(T[] array)
	in
	{
		assert(array !is null);
	}
	body
	{
		if(theSize == 0)
			return;

		if(theHead < theTail)
		{
			Array.copy!(T)(theArray[theHead..$], array[0..$], theSize);
		}
		else
		{
			Array.copy!(T)(theArray[theHead..$], array[0..$], theArray.length - theHead);
			Array.copy!(T)(theArray[0..$], array[theArray.length-theHead..$], theTail);
		}
	}

	/*
	 * 实现 IQueue(T) 接口。
	 */

	private final void setCapacity(int newSize)
	{
		assert(newSize > theSize);

		T[] array = new T[newSize];

		if(theSize > 0)
			this.toArray(array);

		theArray = array;
		theHead = 0;
		theTail = theSize;
		theVersion++;
	}

	/**
	 * 将对象添加到队列的结尾处。
	 * Params:
	 * 		item = 要添加到队列的对象。对于引用类型，该值可以为 null 。
	 * Comments:
	 * 		如果 count 已经等于容量，则会通过自动重新分配内部数组使队列的容量增加，
	 * 		并且在添加新元素之前将现有元素复制到新数组中。
	 *
	 * 		如果 count 小于内部数组的容量，则此方法的运算复杂度是 O(1)。
	 * 		如果需要重新分配内部数组以容纳新元素，则此方法的运算复杂度成为 O(n)，其中 n 为 count。
	 */
	public final bool enqueue(T item)
	{
		if(theSize == theArray.length)
		{
			auto newSize = theSize * 2;
			auto size = newSize > defaultCapacity ? newSize : defaultCapacity;

			assert(size <= int.max);
			assert(size > 0);

			this.setCapacity(size);
		}

		theArray[theTail] = item;

		if(++theTail == theArray.length)
			theTail = 0;

		theSize++;
		theVersion++;
		return true;
	}

	/**
	 * 移除并返回位于队列开始处的对象。
	 * Returns:
	 * 		从队列开头移除的对象。
	 * Throws:
	 * 		InvalidOperationException，当队列为空时。
	 */
	public final T dequeue()
	{
		auto value = peek();

		theArray[theHead] = T.init;

		if(++theHead == theArray.length)
			theHead = 0;

		theSize--;
		theVersion++;

		return value;
	}

	/**
	 * 返回位于队列开始处的对象但不将其移除。
	 * Returns:
	 * 		位于队列开头的对象。
	 * Throws:
	 * 		InvalidOperationException，当队列为空时。
	 */
	public final T peek()
	{
		if(this.isEmpty())
		{
			throw new InvalidOperationException("The queue is empty.");
		}

		return theArray[theHead];
	}

	/**
	 * 从队列中移除所有对象。
	 * Comments:
	 * 		count 被设置为零，并且队列中的元素对其他对象的引用也被释放。
	 */
	public final void clear()
	{
		if(theSize > 0)
		{
			if(theHead < theTail)
			{
				Array.clear!(T)(theArray[theHead..theTail]);
			}
			else
			{
				Array.clear!(T)(theArray[theHead..$]);
				Array.clear!(T)(theArray[0..theTail]);
			}

			theHead = theTail = theSize = 0;
			theVersion++;
		}
	}

	/**
	 * 将对象添加到队列的结尾处。
	 * Params:
	 * 		item = 要添加到队列的对象。对于引用类型，该值可以为 null 。
	 */
	public final bool tryEnqueue(T item)
	{
		return this.enqueue(item);
	}

	/**
	 * 尝试移除并返回位于队列开始处的对象。
	 * Params:
	 * 		item -> 位于队列开头的对象。假如操作不成功，item 为其类型初始值。
	 * Returns:
	 * 		表明该操作是否成功。成功返回 true ，否则返回 false 。
	 */
	public final bool tryDequeue(out T item)
	{
		if(isEmpty())
		{
			item = T.init;
			return false;
		}

		item = theArray[theHead];

		theArray[theHead] = T.init;

		if(++theHead == theArray.length)
			theHead = 0;

		theSize--;
		theVersion++;

		return true;
	}

	/**
	 * 尝试返回位于队列开始处的对象但不将其移除。
	 * Params:
	 * 		item = 位于队列开头的对象。假如操作不成功，item 为其类型初始值。
	 * Returns:
	 * 		表明该操作是否成功。成功返回 true ，否则返回 false 。
	 */
	public final bool tryPeek(out T item)
	{
		if(isEmpty())
		{
			item = T.init;
			return false;
		}

		item = theArray[theHead];
		return true;
	}

	/*
	 * 其他方法。
	 */

	/**
	 * 如果元素数小于当前容量的 90%，将容量设置为队列中的实际元素数。
	 * Comments:
	 * 		如果不向集合中添加新元素，则此方法可用于最小化集合的内存开销。
	 * 		但是，重新分配和复制较大队列的开销可能很大。
	 *
	 * 		因此，如果该列表大于容量的 90%，则 trimExcess 方法将不执行任何操作。
	 * 		这样可以避免为获得相对较少的收益而产生大量重新分配开销。
	 */
	public final void trimExcess()
	{
		auto size = cast(int)(theArray.length * 0.9);
		if( size > theSize )
			this.setCapacity(size);
	}
}

unittest
{
	class QueueTest
	{
		void testCtor()
		{
			auto a = new Queue!(int)();
			auto b = new Queue!(int)(1);
			auto c = new Queue!(Object)();
			auto d = new Queue!(Object)(1);
			auto e = new Queue!(Object)(0);
		}

		void testCtorEx()
		{
			try
			{
				auto a = new Queue!(int)(-1);
			}
			catch(Error e)
			{
				assert(true);
			}
		}

		void testCtorEnum()
		{
			auto list = new ArrayList!(int)();
			list.add(1);
			list.add(2);
			list.add(3);

			auto queue = new Queue!(int)(list);

			assert(queue.dequeue() == 1);
			assert(queue.dequeue() == 2);
			assert(queue.dequeue() == 3);
		}

		void testCtorEnumNull()
		{
			try
			{
				auto queue = new Queue!(int)(null);
			}
			catch(Error e)
			{
				assert(true);
			}
		}

		void testClear()
		{
			auto queue = new Queue!(int)();

			queue.clear();

			assert(queue.count == 0);

			queue.enqueue(1);
			queue.enqueue(2);

			assert(queue.count == 2);

			queue.clear();

			assert(queue.count == 0);

			auto enumerator = queue.getEnumerator();

			queue.clear();

			try
			{
				enumerator.reset();
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testContains()
		{
			auto queue = new Queue!(int)();

			assert( !queue.contains(1) );

			queue.enqueue(1);

			assert( queue.contains(1) );
			assert( !queue.contains(0) );
		}

		void testToArray()
		{
			auto array = new int[3];
			auto queue = new Queue!(int)();

			queue.enqueue(1);
			queue.enqueue(2);

			array[0] = 10;

			queue.toArray(array[1..$]);

			assert(array[0] == 10);
			assert(array[1] == 1);
			assert(array[2] == 2);
		}

		void testPeek()
		{
			auto queue = new Queue!(int)();

			queue.enqueue(1);

			assert( queue.peek() == 1 );
			assert( queue.count == 1 );
		}

		void testPeekEx()
		{
			auto queue = new Queue!(int)();

			try
			{
				queue.peek();
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}

			queue.enqueue(1);
			queue.dequeue();

			try
			{
				queue.peek();
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testTryPeek()
		{
			auto queue = new Queue!(int)();
			queue.enqueue(1);
			int value;
			bool isGetted;
			isGetted = queue.tryPeek(value);

			assert(value == 1 && isGetted == true);

			queue.dequeue();

			// 注意，这里不会产生异常。
			isGetted = queue.tryPeek(value);

			assert(value == 0 && isGetted == false);
		}

		void testDequeue()
		{
			auto queue = new Queue!(int)();
			queue.enqueue(1);

			assert(queue.dequeue() == 1);
			assert(queue.count == 0);
		}

		void testDequeueEx()
		{
			auto queue = new Queue!(int)();

			try
			{
				queue.dequeue();
			}
			catch(InvalidOperationException e)
			{
				assert(true);
			}
		}

		void testTryDequeue()
		{
			auto queue = new Queue!(int)();

			queue.enqueue(1);

			int value;
			bool isGetted;

			isGetted = queue.tryDequeue(value);

			assert( isGetted == true && value == 1);

			// 注意，这里不会产生异常。
			isGetted = queue.tryDequeue(value);

			assert( isGetted == false && value == 0);
		}

		void testEnqueue()
		{
			auto queue = new Queue!(int)();

			queue.enqueue(1);

			assert(queue.count == 1);

			auto b = queue.tryEnqueue(2);

			assert(queue.count == 2 && b == true);

			for(auto i = 0; i < 100; i++)
			{
				queue.enqueue(i);
			}

			assert(queue.count == 102);
		}

		void testEnumerator()
		{
			auto queue = new Queue!(int)();

			foreach(item; queue)
			{
			}
		}

		void testTrimExcess()
		{
			auto queue = new Queue!(int)();

			queue.trimExcess();

			assert(queue.count == 0);

			queue.enqueue(1);
			queue.enqueue(2);

			assert(queue.count == 2);

			queue.trimExcess();

			assert(queue.count == 2);

			queue.dequeue();
			queue.dequeue();

			queue.trimExcess();

			assert(queue.count == 0);
		}
	}

	QueueTest test = new QueueTest();
	test.testCtor();
	test.testCtorEx();
	test.testCtorEnum();
	test.testCtorEnumNull();
	test.testClear();
	test.testContains();
	test.testToArray();
	test.testPeek();
	test.testPeekEx();
	test.testTryPeek();
	test.testDequeue();
	test.testDequeueEx();
	test.testTryDequeue();
	test.testEnqueue();
	test.testEnumerator();
	test.testTrimExcess();
}